import java.util.*;

public class Main {
    public static void main(String[] args) {
        ArrayList<NFAFunction> NFA = new ArrayList<NFAFunction>();
        ArrayList<DFAFunction> DFA = new ArrayList<DFAFunction>();
        readtNFA(NFA, DFA);
        findFirst(NFA, DFA);
        while (getNewDFAFunction(NFA, DFA) == 1)
            ;
        printfDFA(DFA);
        return;
    }

    public static void findFirst(ArrayList<NFAFunction> NFA, ArrayList<DFAFunction> DFA) {
        int NFAFunctionNum = NFA.size();
        DFAFunction first = new DFAFunction();
        first.beginning = NFA.get(0).beginning + "";
        first.str = NFA.get(0).str + "";
        first.end = NFA.get(0).end + "";
        DFA.add(first);
        for (int i0 = 1; i0 <= NFAFunctionNum - 1; i0++) {
            first = new DFAFunction();
            first.beginning = NFA.get(i0).beginning + "";
            if (first.beginning.equals(DFA.get(0).beginning)) {
                first.str = NFA.get(i0).str + "";
                int DFAFunctionNum = DFA.size();
                for (int i1 = 0; i1 <= DFAFunctionNum - 1; i1++) {
                    if (first.str.equals(DFA.get(i1).str))
                        return;
                }
                first.end = NFA.get(i0).end + "";
                DFA.add(first);
            }
        }
        return;
    }

    public static void readtNFA(ArrayList<NFAFunction> NFA, ArrayList<DFAFunction> DFA) {
        Scanner cin = new Scanner(System.in);
        char beginning;// 起点
        String end = new String();// 终点的集合
        String str = new String();// 输入
        int N = cin.nextInt();// 转移函数个数
        while (N > 0) {
            beginning = cin.next().charAt(0);
            str = cin.next();
            end = cin.next();
            NFAFunction current = new NFAFunction(beginning, end, str);
            NFA.add(current);
            N--;
        }
        cin.close();
        return;
    }

    public static int getNewDFAFunction(ArrayList<NFAFunction> NFA, ArrayList<DFAFunction> DFA) {
        int i1;// 判断是否为新的起点
        ArrayList<String> newBeginning = new ArrayList<String>();
        String current = new String();
        int DFAFunctionNum = DFA.size();
        for (int i0 = 0; i0 <= DFAFunctionNum - 1; i0++) {
            current = DFA.get(i0).end;
            for (i1 = 0; i1 <= DFAFunctionNum - 1; i1++)
                if (current.equals(DFA.get(i1).beginning))
                    break;
            if (i1 == DFAFunctionNum)
                newBeginning.add(current);
        }
        int newBeginningNum = newBeginning.size();
        if (newBeginningNum == 0)
            return 0;
        for (int i2 = 0; i2 <= newBeginningNum - 1; i2++) {
            ArrayList<String> strs = new ArrayList<String>();
            ArrayList<String> otherstrs = new ArrayList<String>();
            if (strs.size() == 0) {
                DFAFunction newDFAFunction = new DFAFunction();
                newDFAFunction.beginning = newBeginning.get(i2);
                newDFAFunction.findEnd(NFA, strs, otherstrs);
                DFA.add(newDFAFunction);
            }
            for (int i3 = 0; i3 <= otherstrs.size() - 1; i3++) {
                DFAFunction newDFAFunction = new DFAFunction();
                newDFAFunction.beginning = newBeginning.get(i2);
                newDFAFunction.str = otherstrs.get(i3);
                newDFAFunction.findEnd(NFA, strs, otherstrs);
                DFA.add(newDFAFunction);
            }
        }
        return 1;
    }

    public static void printfDFA(ArrayList<DFAFunction> DFA) {
        int DFAFunctionNum = DFA.size();
        System.out.println("开始状态\t输入\t结束状态");
        for (int i0 = 0; i0 <= DFAFunctionNum - 1; i0++)
            System.out.println(DFA.get(i0).beginning + "\t" + DFA.get(i0).str + "\t" + DFA.get(i0).end);
        return;
    }
}

class DFAFunction {// DFA转移函数
    public String beginning = new String();// 起点
    public String end = new String();// 终点
    public String str = new String();// 输入

    public void findEnd(ArrayList<NFAFunction> NFA, ArrayList<String> strs, ArrayList<String> otherstrs) {// 根据起点和状态转移表找到终点
        int length = beginning.length();
        int NFAFunctionNum = NFA.size();
        for (int i0 = 0; i0 <= length - 1; i0++) {
            char oneBeginning = beginning.charAt(i0);
            for (int i1 = 0; i1 <= NFAFunctionNum - 1; i1++) {
                if (NFA.get(i1).beginning == oneBeginning) {
                    if (NFA.get(i1).str.equals(this.str) || this.str.equals("")) {
                        String endDiffernt = findDifferent(NFA.get(i1).end, this.end);
                        this.end = this.end + endDiffernt;
                        String strDiffernt = findDifferent(NFA.get(i1).str, this.str);
                        this.str = this.str + strDiffernt;
                        strs.add(this.str);
                    } else {
                        String newstr = new String();
                        newstr = NFA.get(i1).str;
                        int strsNum = strs.size(), otherstrsNum = otherstrs.size(), ifAdd = 1;
                        for (int i2 = 0; i2 <= strsNum - 1; i2++) {
                            if (strs.get(i2).equals(newstr)) {
                                ifAdd = 0;
                                break;
                            }
                        }
                        for (int i3 = 0; i3 <= otherstrsNum - 1; i3++) {
                            if (otherstrs.get(i3).equals(newstr)) {
                                ifAdd = 0;
                                break;
                            }
                        }
                        if (ifAdd == 1)
                            otherstrs.add(newstr);
                    }
                }
            }
        }
        return;
    }

    public String findDifferent(String A, String B) {// 返回A中B没有的字符
        String differnt = new String();
        int length = A.length();
        for (int i0 = 0; i0 <= length - 1; i0++) {
            char oneletter = A.charAt(i0);
            if (B.indexOf(oneletter) == -1)
                differnt = differnt + oneletter;
        }
        return differnt;
    }
}

class NFAFunction {// NFA转移函数
    public char beginning;// 起点
    public String end = new String();// 终点的集合
    public String str = new String();// 输入

    public NFAFunction(char beginning, String end, String str) {
        this.beginning = beginning;
        this.end = end;
        this.str = str;
    }
}